package com.wrial.kind.hot;
/*
 * @Author  Wrial
 * @Date Created in 10:11 2020/8/10
 * @Description
 * 输入: n = 5, m = 3 输出: 3
 * 例如，0、1、2、3、4这5个数字组成一个圆圈
 * 从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
 */

public class LastRemaining {
    /**
     * 数学法：
     * 动态规划
     * f(N,M) = (f(N-1,M)+M)%i
     */
    public int lastRemaining(int n, int m) {
        int ans = 0;
        //i=1时必死 i代表进行恢复的个数  ans代表恢复的结果
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}
